<?php

/**
 * 三数之和
 * Class Solution
 */
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $resArr=[];//结果集合
        //排序
        sort($nums);

        $len=sizeof($nums);
        //遍历第一个数-肯定是负数或0
        for($i=0;$i<$len;$i++){
            if($i>0 && $nums[$i]==$nums[$i-1]){
                continue;
            }
            $one=$nums[$i];
            if($one>0){
                break;
            }
            $target=0-$one;
            //双指针查找和
            $left=$i+1;
            $right=$len-1;
            while($left<$right){
                $leftNum=$nums[$left];
                $rightNum=$nums[$right];
                if($leftNum+$rightNum==$target){
                    $resArr[]=[$one,$leftNum,$rightNum];
                    while($left<$right && $nums[$left]==$nums[$left+1]) $left++;
                    while($left<$right && $nums[$right]==$nums[$right-1]) $right--;
                    $left++;
                    $right--;
                }elseif($leftNum+$rightNum>$target){
                    $right--;
                }else{
                    $left++;
                }
            }
        }

        return $resArr;
    }
}

